package leetcode.D700.T652;

import util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-15 17:15:17 星期二
 */

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        Map<String, Integer> cnt = new HashMap<>();
        getSerial(result, cnt, root);
        return result;
    }

    private String getSerial(List<TreeNode> result, Map<String, Integer> cnt, TreeNode root) {
        if (root == null)
            return "";
        String s = root.val + "," + getSerial(result, cnt, root.left) + "," + getSerial(result, cnt, root.right);
        cnt.put(s, cnt.getOrDefault(s, 0) + 1);
        if (cnt.get(s) == 2)
            result.add(root);
        return s;
    }
}